package horseJump;



/**
 * 源于彭正国罚他们跳马
 * 跳马 跳到那个位置有多少种解法
 *      1）创建棋盘chessBoard，是一个二维数组
 *      3）遍历ArrayList中存放的所有位置，看看那个可以走通，继续走，走不通就回朔
 *      假设现在不能回退(前进便不能后退)
 */
public class HorseJump {
    private static int X; //棋盘列数
    private static int Y; //棋盘行数
    private static boolean visited[]; //标记棋盘的各个位置是否访问过
    private static int STEP = 1;
    // 定义共有多少种放置🐎的算法
    private static int COUNT = 1;
    // 这种策略规定8个方向都可以走 见题目而定
    static int []dx = {-2,-1,1,2,-2,-1,1,2};
    static int []dy = {-1,-2,-2,-1,1,2,2,1};
    static int num = 1;
    public static void main(String[] args) {
        System.out.println("骑士周游：");
        X = 3;
        Y = 9;
        int row = 1; //骑士初始行
        int col = 1; //骑士初始列
        int i = X;
        int j = Y;
        //创建棋盘
        int[][] chessboard = new int[X][Y];

        //初始值都为false
        visited = new boolean[X * Y];
        // 将第一颗棋子置为true 避免回朔走到
        visited[(row-1)*Y + col-1] = true;
        long start = System.currentTimeMillis();
        jump(chessboard, row -1, col - 1, i-1,j-1);
        long end = System.currentTimeMillis();
        System.out.println("共耗时 " + (end - start) + " 毫秒");
        System.out.println(num);
    }
    public static void jump(int [][]chessBoard,int row,int col,int k,int j){
      if (row==k && col ==j){
          display(chessBoard);
          return;
      }
        for (int i = 0; i < dx.length ; i++) {
            int newX = row+dx[i];
            int newY = col + dy[i];
            if ((newX>=0 && newX<X && newY>=0 && newY>=0 &&newY<Y )&& !visited[newX * Y + newY]){
                visited[newX*Y + newY]=true;
                // 把棋子走的路径标注起来
                chessBoard[newX][newY] = STEP++;
                jump(chessBoard,newX,newY,k,j);
                // 走不通 回朔置0
                chessBoard[newX][newY] = 0;
                STEP--;
                visited[newX * Y + newY] = false;
            }
        }
    }

    public static void display(int[][]chessBoard){
        System.out.println("第"+num+++"次走法");
        //输出棋盘情况
        for (int[] rows : chessBoard) {
            for (int step : rows) {
                System.out.print(step + "\t");
            }
            System.out.println();
        }
    }

}
